#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/10/06
# @Author   :Changshu
# @File     :practice_219.py
# 219.存在重复元素 II
# 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
'''这个方法超时了，时间复杂度：O(n*k)
def containsNearbyDuplicate(nums: list, k: int) -> bool:
	n=len(nums)
	for i in range(0,n):
		count = [nums[i]]
		for j in range(1,k+1):
			t=i+j
			if t>=n:
				continue
			if nums[t] in count:
				return True
			else:
				count.append(nums[t])
	return False
'''

'''使用字典，保存数值和索引'''
def containsNearbyDuplicate(nums: list, k: int) -> bool:
	d={}
	for i in range(0,len(nums)):
		t=nums[i]
		if t in d:
			if i-d[t]<=k:
				return True
		d[t]=i
	return False

if __name__ == '__main__':
	nums = [1,2,3,1,2,3]
	k=2
	b=containsNearbyDuplicate(nums,k)
	print(b)
